home *** CD-ROM | disk | FTP | other *** search
/ TOS Silver 2000 / TOS Silver 2000.iso / programm / MM2_DEV / S / MYUTIL / HASHTEST.M < prev    next >
Encoding:
Text File  |  1993-07-11  |  2.4 KB  |  85 lines
  1. MODULE HashTest;
  2.  
  3. FROM SYSTEM IMPORT TSIZE;
  4. FROM Storage IMPORT ALLOCATE;
  5. FROM Strings IMPORT StrEqual;
  6.  
  7. TYPE
  8.   Str = ARRAY [0..5] OF CHAR;
  9.   
  10.   PtrItem = POINTER TO Item;
  11.   
  12.   Item = RECORD
  13.     next: PtrItem;
  14.     data: Str;
  15.   END;
  16.   
  17.   HashIdx = [0..MAX(INTEGER)];
  18.   
  19.   PtrHashTbl = POINTER TO ARRAY HashIdx OF PtrItem;
  20.  
  21. VAR hashTblPtr: PtrHashTbl;
  22.     hashTblSize: LONGCARD;
  23.  
  24. PROCEDURE Init (hashSize: CARDINAL): BOOLEAN;
  25.   (* 'hashSize' sollte eine Primzahl sein *)
  26.   VAR n: HashIdx;
  27.   BEGIN
  28.     hashTblSize:= hashSize;
  29.     ALLOCATE (hashTblPtr, hashTblSize * TSIZE (PtrItem));
  30.     IF hashTblPtr = NIL THEN
  31.       RETURN FALSE
  32.     END;
  33.     FOR n:= 0 TO hashSize-1 DO
  34.       hashTblPtr^[n]:= NIL
  35.     END;
  36.     RETURN TRUE
  37.   END Init;
  38.  
  39. PROCEDURE hashValue (VAR s: ARRAY OF CHAR): HashIdx;
  40.   VAR x: LONGCARD; n: CARDINAL; ch: CHAR;
  41.   BEGIN
  42.     x:= 0;
  43.     n:= 0;
  44.     LOOP
  45.       ch:= s[n];
  46.       IF ch = 0C THEN EXIT END;
  47.       IF ch >= 'A' THEN DEC (ch, ORD('A')) END;
  48.       x:= x * 26 + VAL (LONGCARD, ORD (ch));
  49.       INC (n);
  50.       IF n > HIGH (s) THEN EXIT END
  51.     END;
  52.     RETURN VAL (HashIdx, x MOD hashTblSize)
  53.   END hashValue;
  54.  
  55. PROCEDURE Add (s: Str): BOOLEAN;
  56.   VAR idx: HashIdx; item: PtrItem;
  57.   BEGIN
  58.     idx:= hashValue (s);
  59.     item:= hashTblPtr^[idx];
  60.     WHILE item # NIL DO
  61.       IF StrEqual (item^.data, s) THEN
  62.         RETURN FALSE
  63.       END;
  64.       item:= item^.next
  65.     END;
  66.     NEW (item);
  67.     item^.next:= hashTblPtr^[idx];
  68.     item^.data:= s;
  69.     hashTblPtr^[idx]:= item;
  70.     RETURN TRUE
  71.   END Add;
  72.  
  73. BEGIN
  74.   IF ~Init (2) THEN HALT END;
  75.   IF ~Add ("AA") THEN HALT END;
  76.   IF ~Add ("AB") THEN HALT END;
  77.   IF ~Add ("AC") THEN HALT END;
  78.   IF  Add ("AA") THEN HALT END;
  79.   IF  Add ("AB") THEN HALT END;
  80.   IF  Add ("AC") THEN HALT END;
  81.   
  82. END HashTest.
  83. ə
  84. (* $FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8Ç$000005A3T.......T.......T.......T.......T.......T.......T.......T.......T.......T.......$000005A3$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8$FFEC07E8äÇÇ*)
  85.